package alo.p19;


/**
 * @ClassName LCSLength
 * @Description 最长公共子序列
 * @Author Fanxc
 * @DATE 2021/3/14 16:55
 * @Version 1.0
 */
public class LCSLength {
    int[][] LCS=new int[1024][1024];
    int LCSLength(int[] X,int m,int[] Y,int n){

        //初始化二维数组
        for (int i = 0; i < m+1; i++) {
            LCS[i][0] = 0;
        }
        for (int i = 0; i < n+1; i++) {
            LCS[0][i] = 0;
        }
        for (int i = m-1; i >=0; i--) {
            for (int j=n-1;j >=0;j--){
                LCS[i][j]=LCS[i+1][j+1];
                if (X[i]==Y[j]){
                    LCS[i][j]++;
                }
                if (LCS[i][j+1]>LCS[i][j]){
                    LCS[i][j]=LCS[i][j+1];
                }
                if (LCS[i+1][j]>LCS[i][j]){
                    LCS[i][j]=LCS[i+1][j];
                }
            }
        }
        return LCS[0][0];
    }


}
